/*
 * @lc app=leetcode.cn id=1499 lang=typescript
 *
 * [1499] 满足不等式的最大值
 */

// @lc code=start
function findMaxValueOfEquation(points: number[][], k: number): number {
  const m = points.length;
  // 单调递减队列
  const deque = [0];
  let ans = Number.NEGATIVE_INFINITY;

  for (let i = 1; i < m; i++) {
    // 不在k的范围内，头部出队
    while (deque.length && points[i][0] - points[deque[0]][0] > k) {
      deque.shift();
    }
    // 如果队列还有元素，计算答案
    if (deque.length) {
      const xi = points[deque[0]][0];
      const yi = points[deque[0]][1];
      const xj = points[i][0];
      const yj = points[i][1];
      ans = Math.max(ans, xj + yj + yi - xi);
    }
    // 不满足单调性，处理队尾出队
    while (
      deque.length &&
      points[i][1] - points[i][0] >
        points[deque[deque.length - 1]][1] - points[deque[deque.length - 1]][0]
    ) {
      deque.pop();
    }
    // 入队
    deque.push(i);
  }

  return ans;
}
// @lc code=end
